#include "../tools.h"

/**
 * 根据字符出现频率排序
 * Input:  "tree"
 * Output: "eert" or "eetr"
 *  
 */

class Solution {
public:
    string frequencySort(string s) {
        unordered_map<char, int> m;
        vector<pair<char, int>> v;
        string res;
        // 填充map
        for(auto& c: s)
            m[c]++;
        
        // for(auto& [k, v]: m)
        //     cout << k << " - " << v << endl;

        // map2vector<pair<char, int>>
        for(auto& p: m)
            v.emplace_back(p);


        // sort
        sort(v.begin(), v.end(), [](const pair<char, int> a, const pair<char, int> b)
        {return a.second > b.second;});

        // for(auto& e: v)
        //     cout << e.first << " - " << e.second << endl;

        // 遍历vector to string
        for(auto& e: v)
            for(int i = 0; i < e.second; ++i)
                res += e.first;
        return res;
    }
};



int main(int argc, char const *argv[])
{
    Solution s;

    string str = "Aabb";
    string res = s.frequencySort(str);

    cout << res << endl;

    return 0;
}
